package Algorithm.interview;

/**
 * @Author self
 * @Date 2024/10/6 18:24
 * @Describe 反转链表是一个常见的算法问题，可以通过迭代或递归两种方式来实现。
 * 下面是使用 Java 实现反转链表的两种方法。
 */
public class ReverseLinkedList {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }
    /*
    方法 1：迭代法
    */
    public ListNode reverseList1(ListNode head) {
        ListNode prev = null;
        ListNode current = head;

        while (current != null) {
            ListNode nextTemp = current.next; // 保存下一个节点
            current.next = prev;               // 反转当前节点的指针
            prev = current;                    // 移动 prev 和 current
            current = nextTemp;
        }
        return prev; // prev 现在是新的头节点
    }

    /*
    方法 2：递归法
    */
    public ListNode reverseList2(ListNode head) {
        // 基础情况
        if (head == null || head.next == null) {
            return head;
        }

        ListNode newHead = reverseList2(head.next); // 递归反转后面的链表
        head.next.next = head; // 将当前节点指向它的前一个节点
        head.next = null; // 将当前节点的 next 设置为 null
        return newHead; // 返回新的头节点
    }

    public static void main(String[] args) {
        // 创建一个链表: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ReverseLinkedList rll = new ReverseLinkedList();
        ListNode reversedHead = rll.reverseList1(head);

        // 打印反转后的链表
        ListNode current = reversedHead;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();

        // 创建一个链表: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(3);
        head2.next.next.next = new ListNode(4);
        head2.next.next.next.next = new ListNode(5);

        ReverseLinkedList rll2 = new ReverseLinkedList();
        ListNode reversedHead2 = rll2.reverseList2(head2);

        // 打印反转后的链表
        ListNode current2 = reversedHead2;
        while (current2 != null) {
            System.out.print(current2.val + " ");
            current2 = current2.next;
        }
    }
}
